package 笔试;


class ListNode {
    int val;
    ListNode next = null;
}

public class 以组为单位反转单链表 {

    public ListNode reverseLinkedList (ListNode head, int n) {
        if (n == 1) {
            //保证翻转1个以上
            return head;
        }
        ListNode res = new ListNode(), result = res;
        res.next = head;
        ListNode pre, post;

        while (head != null) {
            pre = findNextHead(head, n);
            post = pre.next;
            pre.next = null;

            //翻转当前这段
            pre = reverse(head);
            res.next = pre;

            head.next = post;
            res = head;
            head = head.next;
        }

        return result.next;
    }

    //翻转链表
    private ListNode reverse(ListNode head) {
        ListNode pre = null, post = head;
        while (post != null) {
            ListNode tmp = post.next;
            post.next = pre;
            pre = post;
            post = tmp;
        }
        return pre;
    }

    //找到下一截翻转起点 //并与前一段切断
    private ListNode findNextHead(ListNode head, int k) {
        ListNode pre = null;

        while (head != null && k > 0) {
            pre = head;
            head = head.next;
            k--;
        }
        return pre;
    }
}
